package com.leo.datastruct.linear;

import java.util.Arrays;

/**
 *
 * @author xuexiaolei
 * @version 2018年01月31日
 */
public class StringPattern {
    /**
     * 获取KMP算法的next数组
     * @param a
     */
    private static int[] getNext(String a){
        int[] next = new int[a.length()];
        next[0] = -1;
        int k = -1; //匹配到哪个字符了
        int j = 0;  //每一个下标
        while (j < a.length()-1){
            if (k == -1 || a.charAt(j) == a.charAt(k)){
                k++;
                j++;
                next[j] = k;
            }else {
                k = next[k];
            }
        }
        System.out.println("next数组：" + Arrays.toString(next));
        return next;
    }

    /**
     * KMP算法，s为主字符串，p为要查找的字符串
     * @param s
     * @param p
     * @return
     */
    public static int kmpSearch(String s, String p){
        int[] next = getNext(p);
        int i=0, j=0;
        while (i<s.length() && j<p.length()){
            if (j == -1 || s.charAt(i) == p.charAt(j)){//如果成功，继续比较
                i++;
                j++;
            }else {
                //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
                //next[j]即为j所对应的next值
                j=next[j];
            }
        }
        if (j == p.length()){
            return i-j; //匹配成功
        }else {
            return -1;  //匹配失败
        }
    }

    public static void main(String[] args) {
        StringPattern.kmpSearch("ababaefababa", "ababad");
    }
}
